<script>
  let bt = {
    val: 1,
    left: {
      val: 2,
      left: {
        val: 3,
        left: {
          val: 5,
          left: null,
          right: null,
        },
        right: null,
      },
      right: {
        val: 4,
        left: null,
        right: null,
      },
    },
    right: {
      val: 6,
      left: {
        val: 7,
        left: null,
        right: null,
      },
      right: {
        val: 8,
        left: null,
        right: null,
      },
    },
  };
  //先序遍历
  const preorder = (root) => {
    if (!root) return;
    let stack = [root];
    while (stack.length) {
      let n = stack.pop();
      console.log(n.val);
      if (n.right) stack.push(n.right);
      if (n.left) stack.push(n.left);
    }
  };
  // preorder(bt)
  //中序遍历
  const inorder = (root) => {
    if (!root) return;
    let stack = [];
    let p = root;
    while (stack.length || p) {
      while (p) {
        stack.push(p);
        p = p.left;
      }
      let n = stack.pop();
      console.log(n.val);
      p = n.right;
    } 
  };
  // inorder(bt)
  //后序遍历
  const postorder = (root) => {
    if (!root) return;
    let stack = [root];
    let newstack = [];
    while (stack.length) {
      let n = stack.pop();
      newstack.push(n.val)
      if (n.left) stack.push(n.left);
      if (n.right) stack.push(n.right);
    }
    while(newstack.length){
        const n = newstack.pop()
        console.log(n);
    }
  };
  postorder(bt)
</script>
